# 第1节 深度和广度优先究竟是指啥

book = [0 for i in range(0, 101)]
sum = 0
n = 6
e = [[0 for i in range(0, 11)] for j in range(0, 11)]

if __name__ == '__main__':
    print('main')
    # n = int(input('顶点数量'))
    # m = int(input('边数量'))
    n = 5
    m = 5
    bian = [[0, 0], [1, 2], [1, 3], [1, 5], [2, 4], [3, 5]]
    # 初始化二维数组
    for i, v in enumerate(range(0, n + 1)):
        for j, v2 in enumerate(range(0, m + 1)):
            if i == j:
                e[i][j] = 0
            else:
                e[i][j] = 9  # 设9是正无穷
    print(e)
    # 读入顶点之间的边
    # for i, v in enumerate(range(0, m + 1)):
    #     a = int(input("坐标a"))
    #     b = int(input("坐标b"))
    #     e[a][b] = 1
    for i, v in enumerate(bian):
        if i > 0:
            a = bian[i][0]
            b = bian[i][1]
            e[a][b] = 1
            e[b][a] = 1  # 无向图，所以都要设为1
    # 输出图
    for i, v in enumerate(e):
        if 0 < i <= n:
            for j, v2 in enumerate(v):
                if 0 < j <= m:
                    print(v2, end=' ')
            print()
    print()

    # 从1号出发
    book[1] = 1  # 标记1号顶点已经被访问

    # 队列
    que = [0 for i in range(0, 26)]
    head = 1
    tail = 1

    # 从1号顶点出发
    que[tail] = 1
    tail += 1
    book[1] = 1

    # 当队列不为空的时候循环
    while head < tail:
        cur = que[head]
        i = 1
        while i <= n:
            # 判断当前顶点cur到顶点i是否有边，并判断顶点i是否访问过
            if e[cur][i] == 1 and book[i] == 0:
                book[i] = 1
                que[tail] = i
                tail += 1
            i += 1
        if tail > n:
            break  # 当tail大于n，则表明所有的点都被访问过
        head += 1

    # 输出
    i = 1
    while i < tail:
        print('%d' % que[i], end=' ')
        i += 1
